# JavaCollections
Типы коллекций их отличия

В Java 3 наиболее часто используемых типа коллекций: списки (list), наборы (set) и словари, карты, справочники (map).

Список (list).

List расширяет интерфейс Collection. Список хранит любые значения, в том числе повторяющиеся.
Итерация (обход) списка происходит в порядке добавления элементов, т.е. элемент, добавленный первым, при итерации также будет первым.
Реализации интерфейса List – ArrayList и LinkedList.

ArrayList построен на базе массива.

Удобен для операций чтения, доступ по индексу (порядковому номеру элемента) происходит очень быстро.
Сложности возникают при добавлении значений в середину листа, интерфейсу приходится копировать и смещать все последующие по индексу значения, а если ячейки заняты, создавать новый лист (увеличенный размер массива), куда копируются имеющиеся значения и добавляется новое.

Особенности: 
- хранит не уникальные элементы;
- вывод значений упорядочен по вводу.


LinkedList.

LinkedList представляет собой цепочку элементов, в которой каждый элемент имеет ссылку на предыдущий элемент и на следующий. Также имеется ссылка на начало и на конец списка, что позволяет быстро получать доступ к первому и к последнему элементу. Однако при доступе по индексу, необходимо пробежаться по всей цепочке, что в свлучае большого количества записей увеличивает время доступа.
Добавление и удаление элементов происводится заменой ссылок.

Особенности: 

- хранит не уникальные элементы;
- вывод значений упорядочен по вводу.

Хинт! 

В последних версиях Java ArrayList хорошо оптимизирован и на практике можно выбирать его без ущерба для производительности.



Набор (set).

Интерфейс Set представляет собой набор уникальных значений, наследуется от Collection.

HashSet.

В отличие от List не допускает хранения дублей, если значение уже содержится, то дубль просто игнорируется.
При выводе порядок элементов не сохраняется и будет зависеть от значения хэш-функции для каждого элемента.

Особенности:

- хранит только уникальные значения;
- порядок элементов при выводе не зависит от порядка ввода, но и не рандом. Сортирует порядок по Hash каждого элемента. 

LinkedHashSet.

Также хранит только уникальные значения. В отличие от HashSet сохраняет порядок элементов.

TreeSet.

В отличие от первых двух, автоматически сортирует элементы по возрастанию. В случае строк, по алфавиту.

Хинт!

Нужен порядок элементов без дублей, используй LinkedHashSet. А если хочешь автоматически отсортированный вывод, смотри на TreeSet.



Карта (map).

Map представляет собой набор из пар элементов типа «ключ-значение».

HashMap. 

Особенности:

- порядок эелементов не сохраняется.
- при добавлении значения с тем же ключем, имеющееся значение перезатирается новым.

LinkedHashMap.

Особенности:

- сохраняет порядок элементов.

TreeMap.

Особенности:

- автоматически сортирует набор по ключам.

Хинт!

Если хочешь, что бы значение в Map не перезатиралось дублем, используй для добавления вместо put() putIfAbsent(), тогда добавление произойдет только если значение отсутсвует, а имеющееся не перезатрется.


Помимо рассмотренных наиболее популярных реализаций коллекций, существую еще три вида особенных реализаций.



Queue.

Queue - очередь, реализует принцип «first in – first out», т.е. «первым пришёл – первым ушёл». Добавление элементов в очередь делается методом add(), удаление – poll(), получение первого элемента без его удаления – peek().
Две самые простые реализации очереди – это LinkedList и PriorityQueue.
Для LinkedList сохраняется порядок ввода-вывода.
Для PriorityQueue автоматически сортируется по алфавиту, либо по возрастанию.


Stack.

Стек реализует принцип «last in – first out», т.е. «последним пришёл – первым вышел».
Добавление элементов осуществляется методом push(), а удаление методом pop().
Вывод элементов происходит в обратном порядке, начиная с последнего.
Считается устаревшим и не рекомендуется применять в новых проектах!!!


Deque.

Deque современная альтернатива Stack. 
Deque – это сокращение от «double ended queue» (двусторонняя очередь). Deque является расширением интерфейса очереди Queue.
Реализуется с помощью LinkedList и ArrayDeque. Добавление элементов осуществляется методом push(), а удаление методом pop().
ArrayDeque - порядок вывода наоборот, от последнего к первому.


Хинт!

Для простой реализации очереди Queue - выбери LinkedList. Нужно как-то сортировать элементы внутри очереди - PriorityQueue. В иных ситуациях используй - Deque.



SequencedCollection.

В Java 21 появилась новая группа интерфейсов коллекций, самым основным из которых является SequencedCollection.
Это расширение функционала Collection.

Доступны методы: 

- addFirst() и addLast() этот метод аналогичен add().
- getFirst() и getLast() возвращают первый или последний элемент, либо [] or NoSuchElementException если список пуст.
- reversed() инвертирует вывод элементов.
- removeFirst() и removeLast() для удаления, но если список пуст, получим исключение.

По производительности, операции чтения первого и последнего элемента, а также операции добавления и удаления в конец списка в реализациях ArrayList и LinkedList происходят мгновенно.
Добавление и удаление первого элемента в ArrayList гораздо медленее, чем в LinkedList.
Добавление addFirst() в LinkedList требует изменения ссылок (элементы остаются на месте, слева к ним присоединяется новый), это происходит мгновенно. Но в ArrayList нужно сначала сдвинуть все элементы массива вправо, 
чтобы появилось место для первого элемента. Хотя эта операция хорошо оптимизирована, для больших списков вызовет заметную задержку. То же с removeFirst() в ArrayList. Нужно сдвинуть все элементы влево, начиная со второго.
Поэтому, если работаешь с первым элементом, выбирай – LinkedList.



SequencedSet.

Частным случаем SequencedCollection является интерфейс SequencedSet. При этом он переопределяет унаследованный метод reversed(), возвращая не SequencedCollection, а сам SequencedSet.

Доступны теже методы для реализации LinkedHashSet:

- addFirst() и addLast() этот метод аналогичен add().
- getFirst() и getLast() возвращают первый или последний элемент, либо [] or NoSuchElementException если список пуст.
- reversed() инвертирует вывод элементов.
- removeFirst() и removeLast() для удаления, но если список пуст, получим исключение.

Однако для реализации TreeSet addFirst() и addLast() не доступны и вместо них добавляем элементы с помощью add() он сам разберется куда их добавить, первым или вторым - последним.
При этом удалить первый или последний элемент возможно, используюя removeLast() или removeFirst() соотвественно.


SequencedMap.

SequencedMap расширяет стандартный Map, добавляя в него методы для доступа и манипулирования первой и последней парой элементов Map.Entry
Доступны методы:

- putFirst();
- putLast() аналог put();
- reversed().

TreeMap.

TreeMap не поддерживает методы добавления первого и последнего элемента, т.к. ключи сортируются, добавление элементов делаем через put().

Доступны методы:

- pollFirstEntry() удалить первый;
- pollLastEntry() удалить последний;
- sequencedKeySet() получить упорядоченное множество ключей;
- sequencedValues() значений;
- sequencedEntrySet() множество;
- clear() очистить.
